package leetcode.tree_problem;

/**
 * 剑指 Offer 36. 二叉搜索树与双向链表
 * https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
 */
public class 剑指Offer36二叉搜索树与双向链表 {
    public Node treeToDoublyList(Node root) {
       Node rootReturn = treeToDoublyListHelp(root);
       if (rootReturn == null){//判空判空判空，还瞅半天找不出来哪里空
           return null;
       }
       Node head = rootReturn;
       Node tail = head;
       while (tail.right != null){
           tail = tail.right;
       }
       tail.right = head;
       head.left = tail;
       return head;
    }

    public Node treeToDoublyListHelp(Node root){
        if (root == null){
            return null;
        }
        Node leftHead = treeToDoublyListHelp(root.left);//把左子树链表化
        Node leftTail = leftHead;
        while (leftTail != null && leftTail.right != null){
            leftTail = leftTail.right;
        }
        if (leftTail != null){
            leftTail.right = root;
            root.left = leftTail;
        }
        //左边已经完全和根相连了，处理右边子树
        Node rightHead = treeToDoublyListHelp(root.right);//把右子树链表化
        if (rightHead != null){
            root.right = rightHead;
            rightHead.left = root;
        }
        return leftHead == null ? root : leftHead;
    }
}
